#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;


//给定一个整数N,请打印出从1开始到N位的最大数
//例如，给定N位3，则打印出从1到999



//因为不论是整型还是longlong 类型，都有可能越界，所以这里的话就给出字符串模拟数字的方法



//*******************方法一*******************************
//1.每次使数字加一，并且判断是否越界

bool increase_string(char * str)
{
    int len=strlen(str);
    int i=0;
    int cur_char_num=0;
    for(i=len-1;i>=0;--i)
    {
        cur_char_num=(*(str+i))-'0'+1;
        if(cur_char_num==10&&i==0)
        {//说明是第一位已经超过范围了
            return 0;
        }
        if(cur_char_num<10)
        {
           (*(str+i))++;
           break;
        }
        //剩下的就是大于低位加一并且超过范围的情况
        if(cur_char_num>=10)
        {
           *(str+i)='0';//将这一位置为0
        }
        //将上一位加一,然后再判断上一位是否越界
    }
    return 1;
}
//2.打印这个数
void Print_Num(char * str)
{
    int len=strlen(str);
    int i=0;
    for(i=0;i<len;++i)
    {
        if(*(str+i)!='0')
        {
            printf("%s  ",str+i);
            break;
        }
    }
}


void Print_NbitNum_1(int n)
{
    assert(n>0);
    char * str=new char[n+1];
    str[n]='\0';//字符串结束标志
    int len=n;
    int i=0;
    //先将每一位的字符都置为字符0
    for(i=0;i<len;++i)
    {
        str[i]='0';
    }
    while(1)
    {
        int ret=increase_string(str);
        if(ret==0)
        {
            break;//表明已经到最大值
        }
        Print_Num(str);
    }
    delete[] str;//一定不要忘记释放内存
}


//****************************方法二************************
//这里用到了排列组合，从高位开始将字符从0到1进行排列
//采用递归的方法，递归条件是将最低位也进行了设置
void Print_NbitNum_Recursively(char * str,int len,int index)
{
    if(index==len)//递归出口
    {
        Print_Num(str);
        return;
    }
    int i=0;
    for(i=0;i<10;++i)
    {
        str[index]=i+'0';//开始递归处理后面几位的字符
        Print_NbitNum_Recursively(str,len,index+1);
    }
}
void Print_NbitNum_2(int n)
{
    assert(n>0);
    char * str=new char[n+1];
    str[n]='\0';//字符串结束标志
    int len=n;
    int i=0;
    for(i=0;i<len;++i)
    {
        str[i]='0';
    }
    for(i=0;i<10;i++)//注意这里每个字符是从0到9，
    {
        str[0]=i+'0';//将第0位循环设置为0-9
        Print_NbitNum_Recursively(str,len,1);//从第1位开始递归
    }
    delete[] str;
}

void Test_Print_NbitNum()
{
    int n=3;
    //Print_NbitNum_1(n);
    Print_NbitNum_2(n);
}



int main()
{
    Test_Print_NbitNum();
    return 0;
}
